/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author zhong
 *
 */
public class FindandReplacePattern {
	public List<String> findAndReplacePattern(String[] words, String pattern) {
		List<String> res = new ArrayList<>();
		List<List<Integer>> pList = buildPattern(pattern);
		for (String word : words) {
			List<List<Integer>> wList = buildPattern(word);
			// 比较相等
			if (isEqual(pList, wList)) {
				res.add(word);
			}
		}
		return res;
	}

	private boolean isEqual(List<List<Integer>> pList, List<List<Integer>> wList) {
		if (pList.size() != wList.size()) {
			return false;
		}
		for (int i = 0; i < pList.size(); i++) {
			List<Integer> list1 = pList.get(i);
			List<Integer> list2 = wList.get(i);
			if (list1.size() != list2.size()) {
				return false;
			}
			for (int j = 0; j < list1.size(); j++) {
				if (list1.get(j) != list2.get(j)) {
					return false;
				}
			}
		}
		return true;
	}

	private List<List<Integer>> buildPattern(String pattern) {
		HashMap<Character, Integer> char2int = new HashMap<>();
		List<List<Integer>> res = new ArrayList<>();
		for (int i = 0; i < pattern.length(); i++) {
			char ch = pattern.charAt(i);
			if (char2int.containsKey(ch)) {
				res.get(char2int.get(ch)).add(i);
			} else {
				char2int.put(ch, res.size());
				List<Integer> list = new ArrayList<>();
				list.add(i);
				res.add(list);
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] words = { "abc", "deq", "mee", "aqq", "dkd", "ccc" };
		String pattern = "abb";
		System.out.println(new FindandReplacePattern().findAndReplacePattern(words, pattern));
	}

}
